var Placement = {
  /**
   * choose <i>numOfReplicas</i> data nodes for <i>writer</i> 
   * to re-replicate a block with size <i>blocksize</i> 
   * If not, return as many as we can.
   * 
   * @param numOfReplicas: additional number of replicas wanted.
   * @param writer: the writer's machine, null if not in the cluster.
   * @param choosenNodes: datanodes that have been choosen as targets.
   * @param excludedNodes: datanodesthat should not be considered targets.
   * @param blocksize: size of the data to be written.
   * @return array of DatanodeDescriptor instances chosen as target 
   * and sorted as a pipeline.
   */
	chooseTarget: function (dc, numOfReplicas, writer, choosenNodes, excludedNodes, blocksize) {
		this.dc = dc;
		
		if (numOfReplicas == 0 || Object.keys(dc.hosts).length == 0) {
	      return [];
	    }

	    if (!excludedNodes) { excludedNodes = [];}
		if (!choosenNodes) { choosenNodes = []; }

	    var clusterSize = Object.keys(dc.hosts).length;
	    var totalNumOfReplicas = choosenNodes.length + numOfReplicas;
	    if (totalNumOfReplicas > clusterSize) {
	      numOfReplicas -= (totalNumOfReplicas - clusterSize);
	      totalNumOfReplicas = clusterSize;
	    }

	    var maxNodesPerRack = 
	      (totalNumOfReplicas - 1) / Object.keys(this.dc.racks).length + 2;

	    var results = [];
		results.concat(choosenNodes);
	    excludedNodes.concat(choosenNodes);

	    if (!writer.apps['datanode']) { // if writer is also a datanode?
	      writer = null;
	    }

	    var localNode = this.chooseTarget2(
										numOfReplicas, 
										writer, 
										excludedNodes,
										blocksize,
										maxNodesPerRack,
										results);

		results = results.filter(function (x) {
			return this.indexOf(x) == -1;
		}, choosenNodes);

	    // sorting nodes to form a pipeline
	    return this.getPipeline((writer == null)? localNode : writer, results);
	},

	/* choose <i>numOfReplicas</i> from all data nodes */
	chooseTarget2: function (
		numOfReplicas,
		writer,
		excludedNodes,
		blocksize,
		maxNodesPerRack,
		results) 
	{
		var nhosts = Object.keys(this.dc.hosts).length;

		if (numOfReplicas == 0 || nhosts == 0) {
			return writer;
		}

		var numOfResults = results.length;
		var newBlock = (numOfResults == 0);
		if (writer == null && !newBlock) {
			writer = results[0];
		}

		try {
			switch(numOfResults) {
			case 0:
				writer = this.chooseLocalNode(writer, excludedNodes, 
					blocksize, maxNodesPerRack, results);
				if (--numOfReplicas == 0) {
					break;
				}
			case 1:
				this.chooseRemoteRack(1, results[0], excludedNodes, 
					blocksize, maxNodesPerRack, results);
				if (--numOfReplicas == 0) {
					break;
				}
			case 2:
				//if (clusterMap.isOnSameRack(results.get(0), results.get(1))) {
				if (results[0].rack == results[1].rack) {
					this.chooseRemoteRack(1, results[0], excludedNodes,
						blocksize, maxNodesPerRack, results);
				} else if (newBlock) {
					this.chooseLocalRack(results[1], excludedNodes, blocksize, 
						maxNodesPerRack, results);
				} else {
					this.chooseLocalRack(writer, excludedNodes, blocksize,
						maxNodesPerRack, results);
				}
				if (--numOfReplicas == 0) {
					break;
				}
			default:
				this.chooseRandom2(numOfReplicas, this.dc.hosts, excludedNodes, 
					blocksize, maxNodesPerRack, results);
			}
		} catch (e) {
			print("Not able to place enough replicas, still in need of " + numOfReplicas);
		}
		return writer;
	},

	/* choose <i>localMachine</i> as the target.
	* if <i>localMachine</i> is not availabe, 
	* choose a node on the same rack
	* @return the choosen node
	*/
	chooseLocalNode: function(localMachine, excludedNodes, blocksize, maxNodesPerRack, results)
	{
		// if no local machine, randomly choose one node
		if (localMachine == null) {
			return this.chooseRandom(this.dc.hosts, excludedNodes, 
				blocksize, maxNodesPerRack, results);
		}

	    // otherwise try local machine first
	    if (excludedNodes.indexOf(localMachine) == -1) {
	      excludedNodes.push(localMachine);
	      if (this.isGoodTarget(localMachine, blocksize,
	                       maxNodesPerRack, false, results)) {
	        results.push(localMachine);
	        return localMachine;
	      }
	    } 

	    // try a node on local rack
	    return this.chooseLocalRack(localMachine, excludedNodes, 
	                           blocksize, maxNodesPerRack, results);
	  },
	
	/* choose one node from the rack that <i>localMachine</i> is on.
	* if no such node is availabe, choose one node from the rack where
	* a second replica is on.
	* if still no such node is available, choose a random node 
	* in the cluster.
	* @return the choosen node
	*/
	chooseLocalRack: function (localMachine, excludedNodes, blocksize, maxNodesPerRack, results)
	{
	    // no local machine, so choose a random machine
	    if (localMachine == null) {
	      return this.chooseRandom(this.dc.hosts, excludedNodes, 
	                          blocksize, maxNodesPerRack, results);
	    }

	    // choose one from the local rack
	    try {
	      return this.chooseRandom(
	                          localMachine.rack.hosts,
	                          excludedNodes, blocksize, maxNodesPerRack, results);
	    } catch (e1) {
			// find the second replica
			var newLocal = null;
			for (var i = 0; i < results.length; i ++) {
				var nextNode = results[i];
				if (nextNode != localMachine) {
					newLocal = nextNode;
					break;
				}
			}

			if (newLocal != null) {
				try {
					return this.chooseRandom(
						newLocal.rack.hosts,
						excludedNodes, blocksize, maxNodesPerRack, results);
				} catch(e2) {
					//otherwise randomly choose one from the network
					return this.chooseRandom(this.dc.hosts, excludedNodes,
						blocksize, maxNodesPerRack, results);
				}
			} else {
				//otherwise randomly choose one from the network
				return this.chooseRandom(this.dc.hosts, excludedNodes,
					blocksize, maxNodesPerRack, results);
			}
		}
	},
	
	/* choose <i>numOfReplicas</i> nodes from the racks 
	* that <i>localMachine</i> is NOT on.
	* if not enough nodes are availabe, choose the remaining ones 
	* from the local rack
	*/

	chooseRemoteRack: function(numOfReplicas, localMachine, excludedNodes, blocksize, maxReplicasPerRack, results)
	{
		var oldNumOfReplicas = results.length;
		var remoteRackNodes = {};
		// randomly choose one node from remote racks
		try {
			for (var rackname in this.dc.racks) {
				var rack = this.dc.racks[rackname];
				if (rack == localMachine.rack) continue;
				for (var hostname in rack.hosts) {
					remoteRackNodes[hostname] = rack.hosts[hostname];
				}
			}
			this.chooseRandom2(numOfReplicas, remoteRackNodes,
                   excludedNodes, blocksize, maxReplicasPerRack, results);
		} catch (e) {
      		this.chooseRandom2(numOfReplicas-(results.length - oldNumOfReplicas),
				localMachine.rack.hosts, excludedNodes, blocksize, 
				maxReplicasPerRack, results);
		}
	},

	/* Randomly choose one target from <i>nodes</i>.
	* @return the choosen node
	*/
	chooseRandom: function(nodes, excludedNodes, blocksize, maxNodesPerRack, results)
	{
 		var result;
		do {
			var selectedNodes = this.chooseRandom3(1, nodes, excludedNodes);
			if (selectedNodes.length == 0) {
				throw "Not able to place enough replicas";
			}
			result = selectedNodes[0];
		} while(!this.isGoodTarget(result, blocksize, maxNodesPerRack, results));
		results.push(result);
		return result;
	},

	/* Randomly choose <i>numOfReplicas</i> targets from <i>nodes</i>.
	*/
	chooseRandom2: function (numOfReplicas, nodes, excludedNodes, blocksize, maxNodesPerRack, results)
	{
    	var toContinue = true;
		do {
		 	var selectedNodes = this.chooseRandom3(numOfReplicas, nodes, excludedNodes);
			if (selectedNodes.length < numOfReplicas) {
				toContinue = false;
			}
			for(var i = 0; i < selectedNodes.length; i++) {
				var result = selectedNodes[i];
				if (this.isGoodTarget(result, blocksize, maxNodesPerRack, results)) {
					numOfReplicas--;
					results.push(result);
        		}
      		} // end of for
		} while (numOfReplicas > 0 && toContinue);

		if (numOfReplicas > 0) {
			throw "Not able to place enough replicas";
		}
	},

	/* Randomly choose <i>numOfNodes</i> nodes from <i>scope</i>.
	* @return the choosen nodes
	*/
	chooseRandom3: function (numOfReplicas, nodes, excludedNodes) {
		var results =  [];
		var numOfAvailableNodes = Object.keys(nodes).length;
		numOfReplicas = (numOfAvailableNodes < numOfReplicas) ? numOfAvailableNodes:numOfReplicas;
		
		while (numOfReplicas > 0) {
			var rand = Math.floor(this.dc.random.uniform(0, numOfAvailableNodes));
			var choosenNodeName = Object.keys(nodes)[rand];
			var choosenNode = nodes[choosenNodeName];
			if (!choosenNode.apps['datanode']) {
				excludedNodes.push(choosenNode);
				continue;
			}
			if (excludedNodes.indexOf(choosenNode) == -1) {
				results.push(choosenNode);
				excludedNodes.push(choosenNode);
				numOfReplicas--;
			}
		}
		return results;    
	},
	
	isGoodTarget: function () {
		return true;
	},
	
	/* Return a pipeline of nodes.
	* The pipeline is formed finding a shortest path that 
	* starts from the writer and tranverses all <i>nodes</i>
	* This is basically a traveling salesman problem.
	*/
	getPipeline: function (writer, nodes) {
		/*
		if (nodes.length==0) return nodes;
		var index=0;
		if (writer == null || !clusterMap.contains(writer)) {
			writer = nodes[0];
		}
		for(;index<nodes.length; index++) {
			DatanodeDescriptor shortestNode = nodes[index];
			int shortestDistance = clusterMap.getDistance(writer, shortestNode);
			int shortestIndex = index;
			for(int i=index+1; i<nodes.length; i++) {
				DatanodeDescriptor currentNode = nodes[i];
				int currentDistance = clusterMap.getDistance(writer, currentNode);
				if (shortestDistance>currentDistance) {
					shortestDistance = currentDistance;
					shortestNode = currentNode;
					shortestIndex = i;
				}
			}
			//switch position index & shortestIndex
			if (index != shortestIndex) {
				nodes[shortestIndex] = nodes[index];
				nodes[index] = shortestNode;
			}
			writer = shortestNode;
		}
		*/
		return nodes;
	},
	
	/**
	* Verify that the block is replicated on at least 2 different racks
	* if there is more than one rack in the system.
	* 
	* @param lBlk block with locations
	* @param cluster 
	* @return 1 if the block must be relicated on additional rack,
	* or 0 if the number of racks is sufficient.
	*/
	verifyBlockPlacement: function (lBlk, replication, dc) {
		/*
		var numRacks = this.verifyBlockPlacement2(lBlk, Math.min(2,replication), cluster);
		return numRacks < 0 ? 0 : numRacks;
		*/
	},

	/**
	* Verify that the block is replicated on at least minRacks different racks
	* if there is more than minRacks rack in the system.
	* 
	* @param lBlk block with locations
	* @param minRacks number of racks the block should be replicated to
	* @param cluster 
	* @return the difference between the required and the actual number of racks
	* the block is replicated to.
	*/
  	verifyBlockPlacement2: function (lBlk, minRacks, cluster) {
	/*
		var locs = lBlk.getLocations();
		if (locs == null) {
      		locs = new DatanodeInfo[0];
		}
		int numRacks = cluster.getNumOfRacks();
		if(numRacks <= 1) {// only one rack
			return 0;
		}
		minRacks = Math.min(minRacks, numRacks);
		// 1. Check that all locations are different.
		// 2. Count locations on different racks.
		Set<String> racks = new TreeSet<String>();
		for (DatanodeInfo dn : locs) {
			racks.add(dn.getNetworkLocation());
		}
		return minRacks - racks.length;
		*/
  }
	
};
